package leetcode.editor.cn;

//给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。 
// 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
// 示例 1：
//输入：[3,2,3]
//输出：3 
//
// 示例 2： 
//输入：[1,1,1,1,1,2,2,3,3,3,3,3,3,3,3,3]
//输出：2
// 
// 进阶：
//
// 尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
// 
// Related Topics 数组 哈希表 分治 计数 排序 
// 👍 1064 👎 0


import java.util.Arrays;

public class T169MajorityElement {
    public static void main(String[] args) {
        Solution solution = new T169MajorityElement().new Solution();
        int[] nums = {1,1,1,1,1,2,2,3,3,3,3,3,3,3,3,3};
        System.out.println(solution.majorityElement2(nums));


    }
class Solution {
    public int majorityElement1(int[] nums) {
        //将数组从小到大排序
        Arrays.sort(nums);
        //观察发现，经过排序之后，满足条件的数一定在 索引为 nums.length/2 的位置，所以直接返回
        return nums[nums.length / 2];
    }

    //方法二：摩尔投票法
    //如果众数+1，其他数-1，那么所有的数加起来一定大于0
    //我们维护一个候选众数 tag（可以数组中是任意一个），设定一个计数器 count=0，再然后从头至尾，判断数组中的数x与tag是否相等，
    //在判断之前，如果count=0，那么就令tag = x,并将count+1；如果相等则count+1，否则count-1，当count=0时，tag换
    public int majorityElement2(int[] nums) {
        int count = 0 ;
        int tag = 0;
        for (int i = 0; i < nums.length; i++) {
            if (count == 0) {
                tag =nums[i];
                count++;
            }else {
                if (tag == nums[i]) {
                    count++;
                }else {
                    count--;
                }
            }
        }
        return tag;
    }


    /**
     * 分组治法
     * 将数组nums拆成两个数组，那么原数组的众数也一定至少是另外两个数组中某一个数组的众数。
     * 那么我们就可以分别求出拆开之后的两个数组的众数a和b，然后再比较a和b谁是最终的众数。
     * @return
     */
    private int majorityElementRec(int[] nums, int lo, int hi) {
        if (lo == hi) {
            return nums[lo];
        }

        int mid = (hi - lo) / 2 + lo;
        int left = majorityElementRec(nums, lo, mid);
        int right = majorityElementRec(nums, mid + 1, hi);

        if (left == right) {
            return left;
        }

        int leftCount = countInRange(nums, left, lo, hi);
        int rightCount = countInRange(nums, right, lo, hi);
        return leftCount > rightCount ? left : right;
    }
    private int countInRange(int[] nums, int num, int lo, int hi) {
        int count = 0;
        for (int i = lo; i <= hi; i++) {
            if (nums[i] == num) {
                count++;
            }
        }
        return count;
    }


}

}